In the latter half of the twentieth century, there began a phenomenon known as the information revolution. While the information revolution is a historical development broader in scope than any one event or machine, no single device has come to represent the information revolution more than the digital electronic computer. The development of computer systems has surely been a revolution. Each year, computer systems grow faster, store more data, and provide more applications to their users.
A modern computer system typically comprises one or more central processing units (CPU) and supporting hardware necessary to store, retrieve and transfer information, such as communication buses and memory. It also includes hardware necessary to communicate with the outside world, such as input/output controllers or storage controllers, and devices attached thereto such as keyboards, monitors, tape drives, disk drives, communication lines coupled to a network, etc. The CPU or CPUs are the heart of the system. They execute the instructions which form a computer program and directs the operation of the other system components.
From the standpoint of the computer's hardware, most systems operate in fundamentally the same manner. Processors are capable of performing a limited set of very simple operations, such as arithmetic, logical comparisons, and movement of data from one location to another. But each operation is performed very quickly. Sophisticated software at multiple levels directs a computer to perform massive numbers of these simple operations, enabling the computer to perform complex tasks. What is perceived by the user as a new or improved capability of a computer system is made possible by performing essentially the same set of very simple operations, but using software with enhanced function, along with faster hardware.
Almost all modern general purpose computer systems support some form of multi-tasking, in which multiple processes are simultaneously active, and computer system resources, particularly processor resources, are allocated among the different processes. Multi-tasking supports a more efficient use of the various hardware resources by enabling a resource which is temporarily not needed by one process to be used by a different process. Multi-tasking thus increases overall throughput, i.e., overall work performed in a given time.
Multi-tasking inevitably causes contention among the active processes for certain resources. As the number of active processes increases to more fully utilize key resources, this contention becomes more serious. Eventually, the number of active processes can become so large that contention for resources begins to adversely affect performance. In other words, at some point the addition of more active processes will degrade throughput, because the benefit of increased resource utilization is outweighed by the increased contention these additional processes entail.
Resources which are shared by active processes can be either hardware resources (processors, memory space, etc.) or software resources (shared data structures, shared code paths). There are certain resources which, by their nature, are capable of being utilized by multiple processes simultaneously, but which are heavily optimized to operate more efficiently when utilized by a single process at a time. In particular, executable code is generally available for use by multiple processes simultaneously, but there are certain code paths which result in much faster execution if only one process or thread is executing in the code path at any given time.
In such a situation, it would be possible to regulate access to the resource by use of a lock. A lock is a software mechanism by which a single process is granted the exclusive temporary use of a resource, and when finished relinquishes the lock so that the resource may be used by other processes. A lock therefore guarantees that only one process can utilize the resource at a time. However, the granting and relinquishing of locks itself involves considerable overhead. For this reason, locks are typically used only to regulate access to resources which can not be simultaneously accessed, e.g., where simultaneous access could compromise data integrity.
It would be desirable to reduce contention of multiple processes for shared resources, and particularly for software resources, without the high overhead associated with conventional lock mechanisms.